package club.vann.nowcoder;

/**
 * <p>难度：Medium</p>
 * <p>题目：最长公共子序列</p>
 * <p>描述：给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则输出-1。
 * 示例1
 * 输入
 * 复制
 * "1A2C3D4B56","B1D23CA45B6A"
 * 返回值
 * 复制
 * "123456"
 * 说明
 * "123456"和“12C4B6”都是最长公共子序列，任意输出一个。
 * 备注:
 * 1 \leq |str_1|, |str_2| \leq 5\,0001≤∣str
 * 1
 * ​
 *  ∣,∣str
 * 2
 * ​
 *  ∣≤5000</p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-04-20:16:08:46
 */
public class NC92 {
    public static void main(String[] args) {
        NC92 nc = new NC92();

        System.out.println("Result["+TestCase.ANS+"] : " + nc.LCS(TestCase.STRS[0], TestCase.STRS[1]));
    }

    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        // write code here
        char[] ch1 = s1.toCharArray();
        char[] ch2 = s2.toCharArray();

        int len1 = ch1.length;
        int len2 = ch2.length;

        int[][] dp = new int[len1+1][len2+1];

        for(int i = 1; i <= len1; i ++) {
            for(int j = 1; j <= len2; j ++) {
                if(ch1[i-1] == ch2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }

        StringBuilder builder = new StringBuilder();
        int index1 = len1, index2 = len2;
        while(index1 != 0 && index2 != 0) {
            if(ch1[index1-1] == ch2[index2-1]) {
                builder.append(ch1[index1-1]);
                index1 --;
                index2 --;
            } else {
                if(dp[index1-1][index2] > dp[index1][index2-1]) {
                    index1 --;
                } else {
                    index2 --;
                }
            }
        }

        if(builder.length() == 0) {
            return "-1";
        }
        return builder.reverse().toString();
    }

    static class TestCase {
        public static String ANS = "123456";
        public static String[] STRS = {"1A2C3D4B56", "B1D23CA45B6A"};
    }
}
